#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<unordered_map>
using namespace std;

const int inf = 1e18;

long long dfs(int pos, int flag, int pre, vector<vector<int>>& ma, vector<vector<long long>>& dp, vector<vector<bool>>& f, vector<int>& arr, int c)
{
    if (f[pos][flag]) return dp[pos][flag];
    long long ans = 0;
    if (!flag)
    {
        for (auto& x : ma[pos])
        {
            if (x == pre) continue;
            ans += max(dfs(x, 0, pos, ma, dp, f, arr, c), dfs(x, 1, pos, ma, dp, f, arr, c));
        }
    }
    else
    {
        ans += arr[pos];
        for (auto& x : ma[pos])
        {
            if (x == pre) continue;
            ans += max(dfs(x, 0, pos, ma, dp, f, arr, c), dfs(x, 1, pos, ma, dp, f, arr, c) - 2 * c);
        }
    }
    f[pos][flag] = 1;
    dp[pos][flag] = ans;
    return ans;
}

void solve()
{
    int n, c; cin >> n >> c;
    vector<int> arr(n + 5);
    vector<vector<int>> ma(n + 5, vector<int>());
    vector<vector<long long>> dp(n + 5, vector<long long>(2));
    vector<vector<bool>> f(n + 5, vector<bool>(2));
    for (int i = 1; i <= n; i++) cin >> arr[i];
    for (int i = 0; i < n - 1; i++)
    {
        int a, b; cin >> a >> b;
        ma[a].push_back(b);
        ma[b].push_back(a);
    }
    cout << max(dfs(1, 1, -1, ma, dp, f, arr, c), dfs(1, 0, -1, ma, dp, f, arr, c)) << endl;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}